package com.learn.finished;
/*
数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组，找出其中的主要元素。若没有，返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。



示例 1：

输入：[1,2,5,9,5,9,5,5,5]
输出：5
示例 2：

输入：[3,2]
输出：-1
示例 3：

输入：[2,2,1,1,1,2,2]
输出：2
*/


import java.util.Arrays;
import java.util.HashMap;

public class num_Interview17_10 {
    public static void main(String[] args) {
        int[] a ={3,2,3};
        int[] b ={1,2,3};
        int[] c={2,2,2,3,3,4,4};
        int[] d={-1,1,1,1,2,1};

        //System.out.println(c.length/2);

        System.out.println(majorityElement(d));
    }
    //若没有要返回-1
    //==================================================
    //此方法作废
    public static int oldMajorityElement(int[] nums) {
        Arrays.sort(nums);
        for (int num : nums) {
            System.out.print(num);
        }
        System.out.println();
        int num=0;
        int point=nums.length/2;
        num=nums[point];
        if (nums.length>2){
            if ((num==nums[point+1]||num==nums[point-1])&&(num==nums[0]||num==nums[point*2-1])){
                return num;
            }else {
                return -1;
            }

        }else if (nums.length==1){
            return nums[0];
        }
        else {
            return nums[0]==nums[1]?nums[0]:-1;
        }

//        if ((nums.length)%2!=0){
//            return nums[(nums.length)/2];
//        }else {
//            return nums[nums.length/2-1];
//        }
    }
    private static int majorityElement(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int half = nums.length / 2;
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            int count=1;
            if (map.containsKey(num)){
                count=map.get(num);
                count++;
            }
            System.out.println(num+"存储为次数："+count);
            if (count>half)
                return num;
            map.put(num,count);
        }
        return -1;
    }
}
